\documentclass[a4paper,12pt]{article}
\usepackage{fullpage}
\usepackage[british]{babel}
\usepackage[latin1]{inputenc}

\usepackage[boxed]{algorithm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm} \newtheorem{theorem}{Theorem}
\usepackage{color}
\usepackage{clrscode3e}
\usepackage{float}
\usepackage{graphicx}
\usepackage{grffile} % allows spaces in filenames
\usepackage{rotating}
\usepackage{tikz} \usetikzlibrary{trees}
\usepackage{hyperref} % should always be the last package
\hypersetup{colorlinks=true,urlcolor=blue}

% useful colours (use sparingly!):
\newcommand{\blue}[1]{{\color{blue}#1}}
\newcommand{\green}[1]{{\color{green}#1}}
\newcommand{\red}[1]{{\color{red}#1}}

% useful (wrappers for) math symbols:
\newcommand{\Cardinality}[1]{\left\lvert#1\right\rvert}
%\newcommand{\Cardinality}[1]{\##1}
\newcommand{\Implies}{\Rightarrow}
\newcommand{\Inter}{\cap}
\newcommand{\Tuple}[1]{\langle#1\rangle}
%\newcommand{\Tuple}[1]{[#1]}
\newcommand{\Union}{\cup}

% coding convention of AD2 (additions to clrscode3e):
\newcommand{\CounterExample}[1]{\li \Comment \textbf{Counterexample:} #1}
\newcommand{\Example}[1]{\li \Comment \textbf{Example:} #1}
\newcommand{\LoopInvariant}[1]{\Comment \textbf{Invariant:} #1}
\newcommand{\None}{(none)}
\newcommand{\Post}[1]{\li \Comment \textbf{Post:} #1}
\newcommand{\Pre}[1]{\li \Comment \textbf{Pre:} #1}
\newcommand{\ReprConvention}[1]{\Comment \textbf{Representation Convention:} #1}
\newcommand{\ReprInvariant}[1]{\Comment \textbf{Representation Invariant:} #1}
\newcommand{\Signature}[1]{\li \Comment \textbf{Signature:} #1}
\newcommand{\Variant}[1]{\Comment \textbf{Variant:} #1}

% type system:
\newcommand{\Array}[2]{\mathbf{~array}[#1 \twodots #2]}
\newcommand{\Char}{\textbf{char}}
\newcommand{\Int}{\textbf{int}}
\newcommand{\Boolean}{\textbf{boolean}}
\newcommand{\Real}{\textbf{real}}
\newcommand{\String}{\textbf{string}}

\title{Algorithms and Data Structures II \\
    Course 1DL230 at Uppsala University \\
    Spring Semester 2011 \\
    Report for Assignment $3$} % replace n by 1, 2, or 3

\author{Rodrigo GUMUCIO \and Wei HU} % replace by your name(s)

%\date{Month Day, Year}
\date{\today}

\begin{document}

\maketitle

\section{Reliable Communications}
\label{sect:RC}

\subsection{Algorithm}
\label{sect:algo:RC}
Given the communication network modeled as an undirected graph $G=(V,E)$, we want to find a path $<v_0, v_1, ..., v_n>$ with the lowest probability of failure between two given vertices ($v_0$ and $v_n$). The probability that the overall communication between $v_0$ and $v_n$ fails is given by
\[1-(1-f(v_0,v_1)) \cdot \ldots \cdot (1-f(v_{n-1},v_n))\]
Since we need to minimize this quantity, we need 
\[(1-f(v_0,v_1)) \cdot \ldots \cdot (1-f(v_{n-1},v_n))\] to be maximum.
It is safe to apply the logarithm function to this quantity because $\lg(x)$ and $x$ have the same monotonicity, hence we need
\[\lg((1-f(v_0,v_1)) \cdot \ldots \cdot (1-f(v_{n-1},v_n)))
=\lg(1-f(v_0,v_1))+ \ldots + \lg(1-f(v_{n-1},v_n))\] to be maximum.
This means that we need
\[-(\lg(1-f(v_0,v_1))+ \ldots + \lg(1-f(v_{n-1},v_n)))
= (-\lg(1-f(v_0,v_1)))+ \ldots + (-\lg(1-f(v_{n-1},v_n)))\] to be minimum. \\
Furthermore $0 \leq f(v_i,v_j) \leq 1 \Rightarrow 0 \leq 1 - f(v_i,v_j) \leq 1$
$\Rightarrow -(\lg(1 - f(v_i,v_j))) \geq 0$.
As a result, we can use $(-lg(1-f(v_i,v_j)))$ as the weight function of an edge $(v_i,v_j)$ and this problem can be transformed then into a single-source shortest-paths problem on a weighted undirected graph $G = (V, E)$ where all edge weights are non-negative. Moreover, we can replace each undirected edge with two directed edges with opposite directions, then we can use Dijkstra's algorithm to solve this problem. 

\begin{algorithm}
\begin{codebox}
\label{algo:rc1}
\Procname{$\proc{RC}(G,w,u,v)$}
\Signature{$(Graph~G, Weigh\_f_n~w, Vertex~u, Vertex~v) \to List~p$}
\Pre{$G$ is an undirected graph with vertices $G.V$ and edges $G.E$} \\
\quad Each vertex $x$ maintains two attributes: $x.d$ which is an upper bound \\
\quad of a shortest path from $u$ to $x$ and $x.\pi$ which is its predecessor in this path.
\Post{$p$ is a list of vertices which conform the the most reliable}\\
\quad path from $u$ to $v$ \\
\Variant {All loops iterate through a finite set of elements}
\li Let $Q$ be a priority queue of vertices, keyed by their $d$ values
\li $u.d \gets 0$
\li $u.\pi \gets NIL$
\li \For each vertex $x \in G.V-{u}$ \Do 
\li 	$x.\pi \gets NIL$
\li 	$x.d \gets \infty$\End
\li $Q \gets G.V$
\li $found = $ false
\li \While $Q \neq \emptyset$ and not $found$ \Do 
\li 	$s \gets \proc{Extract-Min}(Q)$ 
\li 	\If $s == v$ \Do 
\li 		$found = $ true
\li     \Else
\li 		\For each vertex $x \in G.Adj[s] $ \Do 
\li 			\If $x.d > s.d + w(s,x)$\Do 
\li 				$x.d \gets s.d + w(s,x)$
\li 				$x.\pi \gets s$\End\End\End\End
\li $p = \emptyset$
\li Let $x = v$
\li \While $x.\pi \neq NIL $ \Do
\li 	$p.add(x)$
\li 	$x = x.\pi$	\End
\li \Return $p$
\end{codebox}
\caption{Reliable Communications algorithm}
\end{algorithm}
%~(\ref{algo:bpp1}) and ~(\ref{algo:bpp2}) 
      
\subsection{Analysis}
In this algorithm, it maintains the min-priority queue Q by calling three priority-queue operations: Insert (implicit in line 10), Extract-Min (line 13), and Decrease-Key (implicit, which is called in line 18). In line 7, the for loop will execute for $|V|-1$ times, each in constant time $\Theta(1)$. In line 10, the while loop will execute for $|V|$ times, in this while loop EXTRACT-MIN executes. In line 13, the for loop will execute for $|E|$ times since $\displaystyle\sum_{v \in V} G.Adj[u] = |E|$. In line 9, the Insert will execute for $|V|$ times.Also, there is a function $\lg$ executed in the weight function $w(u,v)$, this will executed for $|E|$ times.In line 24, there is a while loop, which will execute at worst for $|E|$ times, each iteration for constant time.
In total, the running time for this algorithm is\\
$T=\Theta(V)\cdot(T($Extract-Min$)+T($Insert$))+\Theta(E)\cdot (T($Decrease-Key$)+T(\lg))$.\\
Since $T(\lg)$ is not related with $|E|$ or $|V|$, we are not so interested in this part.
And also, $T($Insert$)$ takes constant time each time.
So the running time depends on how the min-priority queue is implemented.\\
\begin{tabular}{l | l | l | l}
	$Q$ & $T($Extract-Min$)$ & $T($Decrease-Key$)$ & Total \\
	array & $O(|V|)$ & $O(1)$ & $O(V^2)$\\
	binary heap & $O(\lg(|V|))$ & $O(\lg(|V|))$ & $O(|E| \cdot \lg(V))$ \\
	Fibonacci heap & $O(\lg(|V|))$ & $O(1)$ & $O(|E| + V \cdot \lg(V))$ \\
	~& amortized & amortized & worst case \\
\end{tabular} 

\section{Party Seating Problem}
\label{sect:RC}

\subsection{Algorithm}
\label{sect:algo:PSP}

We can formulate the two-table as a graph problem as follows. We define a graph $G=(V,E)$ such that $V = \{1, ..., n\}$, i.e. each guest is represented by a vertex ($|V| = n$), and $E = \{(u,v) : u, v \in V \text{ and } u \text{ knows } v\}$. Clearly, $(u,v) \in E$ implies $v$ is in the list of other guests known by $u$, hence $|E| = k$. Furthermore, since the list of guests are symmetric, i.e. $(u,v) \in E$ implies $(v,u) \in E$, we can use only one of these edges and say that $G$ is an undirected graph. Now $|E| = k/2$.

If we can paint the graph with only two colors (representing tables) such that two adjacent nodes do not have the same color, then the problem is solved: we put each guest in a table of the color of its vertex and no guest that he knows will be seated in the same table.

Recall that in a depth first search on an undirected graph, every edge is either a tree edge or a back edge. So, when we consider the adjacency list of a vertex $u$ to explore an edge $(u,v)$, the color of $v$ is either WHITE or GRAY (because a BLACK edge would indicate a forward or cross edge). We can achieve our painting by performing DFS and using two colors instead of GRAY, if we find a back edge $(u,v)$ such that the color assigned to $v$ is the same as the color assigned to $u$, the problem does not have solution for this instance. The idea becomes clearer in the pseudocode, please see Algorithm~2, Algorithm~3 and Algorithm~4.

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\li Let $table$ be a global variable
\end{codebox}
\begin{codebox}
\Procname{$\proc{Divide-Guests}(G)$}
\Signature{$Graph \to (Boolean, List, List)$}
\Pre{$G$ is an undirected graphs with vertices $G.V$ and edges $G.E$} \\
\quad edges represent guests and vertices represent the ``knows'' relationship
\Post{The boolean indicates if the problem has solution, if so two} \\
\quad disjoint lists of vertices are returned (one for each table).\\
\Variant {All loops iterate through a finite set of elements}
\li Let $g$ and $b$ be two empty lists
\li \For each vertex $u \in G.V$ \Do 
\li 	$u.color$ = WHITE \End
\li $table$ = LIGHT\_BLUE
\li \For each vertex $u \in G.V$ \Do
\li 	\If $u.color$ == WHITE \Do
\li 		Let $(ans, g, b) = \proc{Assign-Table}(G,u,g,b)$
\li 		\If not $ans$ \Do
\li 			\Return (false, g, b) \End \End \End
\li \Return (true, g, b)
\end{codebox}
\caption{Party Seating Problem}
\label{algo:PSP1}
\end{algorithm}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{Assign-Table}(G,u,g,b)$}
\Signature{$(Graph, Vertex, List, List) \to (Boolean, List, List)$}
\Pre{$G$ is an undirected graphs with vertices $G.V$ and edges $G.E$} \\
\quad and $u \in G.V$. $g$ and $b$ are lists of vertices representing guests \\
\quad in the same table.
\Post{The boolean indicates if the guests can still be divided in two tables.} \\
\quad If so, the two lists of vertices are updated.\\
\Variant {All loops iterate through a finite set of elements}
\li $u.color$ = table
\li \If table $=$ LIGHT\_BLUE \Do 
\li 	table $=$ LIGHT\_GREEN 
\li \Else 
\li 	table $==$ LIGHT\_BLUE \End
\end{codebox}
\caption{Party Seating Problem (cont.)}
\label{algo:PSP2}
\end{algorithm}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{Assign-Table}(G,u,g,b)$}
\li \For each vertex $v \in G.Adj[u]$ \Do 
\li 	\If not $v.color$ == table \Do 
\li 		\Return (false, g, b)  \End
\li 	\If $v.color$ == WHITE \Do 
\li 		Let $(ans, g, b) = \proc{Assign-Table}(G,v,g,b)$
\li 		\If not $ans$ \Do
\li 			\Return (false, g, b) \End \End \End
\li \If $u.color$ = LIGHT\_BLUE \Do 
\li 	$u.color$ = BLUE
\li 	$b.add(u)$ 
\li \Else
\li 	$u.color$ = GREEN
\li 	$g.add(u)$ \End
\li \Return (true, g, b)
\end{codebox}
\caption{Party Seating Problem (cont.)}
\label{algo:PSP2}
\end{algorithm}
  
If we consider the more general problem saying that the party is attended by $p$ groups of guests, and that there are $q$ tables. All members of a group know each other and no guest knows anyone outside his or her group. Given the sizes of the groups stored in the array $Group[1..p]$ and the sizes of the tables in the array $Table[1..q]$. The problem can be formulated as finding the maximum flow in the following network: \\

\quad\includegraphics[scale=0.6]{exercise.d.png}

If all the edges beginning in the source have its capacity equal to the flow assigned to them, then and only then there is a solution for the problem instance.

\subsection{Analysis}
We are only required to give an analysis for the algorithm that determines whether or not a given set of guests may be seated at two tables, such that no guest knows any other guest seated at the same table. This algorithm is no more than a depth first search using the known algorithm. In the worst case, the instance of the problem has solution and we need to explore all vertices, hence the running time is $O(n + k)$.


\section{Controlling the Maximum Flow}
\label{sect:CMF}
An edge of a flow network is called \emph{sensitive} if decreasing the capacity of this edge results in a
decrease in the maximum flow. The \emph{Maximum Flow Min Cut Theorem (Optimality conditions for max flows)} states that the three following assertions are equivalent:
\begin{enumerate}
\item A flow $x$ is maximum.
\item There is no augmenting path in $G(x)$.
\item There is an $s-t$ cutset $(S, T)$ whose capacity is the flow value of $x$.
\end{enumerate}
As a \emph{corollary} we have that the maximum flow value is equal to the capacity of a minimum cut.
According to the third assertion and the corollary, we can say an edge is \emph{sensitive} if decreasing the capacity of this edge results in a decrease in the capacity of the \emph{minimum cut}. Since decreasing the capacity of any edge from the \emph{minimum cut} results in a decrease in the capacity of the \emph{minimum cut}, each edge of the \emph{minimum cut} is \emph{sensitive}.



\subsection{Algorithm}
Since there is no flow in the residual network from source $s$ to sink $t$ (otherwise there would be an augmenting path the maximum flow is not achived yet), the final residual network is divided into two disjoint sets by the \emph{minimum cut}.

Please, refer to algorithm~5 and algorithm~6.

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{DFS}(G, S, u)$}
\Signature{$(Graph~G, Set~S, Vertex~u) \to Set~S$}
\Pre{$G$ is an undirected graphs with vertices $G.V$ and edges $G.E$.} \\
\quad All edges $G.E$ are marked with color = WHITE 
\Post{The return value is $S$ with the nodes reachable from $u$ in a DFS } \\
\quad marked with color = BLUE \\
\Variant {All loops iterate through a finite set of elements}
\li $u.color$ = GRAY
\li \For each vertex $v \in G.adj[u]$ \Do 
\li		\If $v.color$ = WHITE \Do
\li 		$\proc{DFS}(G,S,v)$ \End \End
\li $u.color$ = BLUE
\li $S \gets S \cup \{u\}$ 
\li \Return $S$
\end{codebox}
\caption{Controlling the Maximum Flow}
\label{algo:CMF}
\end{algorithm}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{CMF}(G(x), G, s)$}
\Signature{$(Graph~G(x), Graph~G, Vertex~s) \to Edge~(u,v)$}
\Pre{$G(x)$ is the final residual network with Maximum flow,} \\
\quad $G$ is the original graph with vertices $G.V$ and non-negative edges $G.E$ \\
\quad $s$ is a vertex in $G$
\Post{The return value is a sensitive edge $(u,v)$ } \\
\Variant {All loops iterate through a finite set of elements}
\li $S \gets \proc{DFS}(G(x),\emptyset, s)$
\li \For each vertex $u$ in $S$\Do
\li 	\For each vertex $v \in G.Adj[u]$ \Do 
\li 		\If $v \not\in S$ \Do 
\li 			\Return $(u,v)$\End\End\End
\end{codebox}
\caption{Controlling the Maximum Flow (cont.)}
\label{algo:CMF}
\end{algorithm}

\subsection{Analysis}
The running time of the DFS function DFS in line $4$ is $\Theta(|V|+|E|)$, since the number of vertices and edges of residual network $G(X)$ and the original network $G$ are the same. The running time for  the for loop of vertices in $G.Adj[u]$ in line $6$, since $\displaystyle\sum_{v \in V} G.Adj[u] = |E|$, is $\Theta(|E|)$. The running time in total is thus $\Theta(|V|+|E|)+\Theta(|E|)=\Theta(|V|+|E|)$, which is linear of $G$.

\section*{Declarations}
\begin{itemize}
	\item The material in this report is solely produced by its authors, except where otherwise indicated and clearly referenced.
	\item All definitions presented when describing the problems were taken from the book ``Introduction to algorithms'' third edition by Cormen, Leiserson, Rivest and Stein.
\end{itemize}

\end{document}
